home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / embedded / simulato / v2_3_mc6.tz / v2_3_mc6 / testfiles / treefnd3.asm < prev    next >
Assembly Source File  |  1994-05-02  |  15KB  |  292 lines
  1. ; Program 3
  2. ; Binary Search Tree
  3. ; Due November 20, 1992
  4.  
  5. ; This program will create and search a binary tree.  The program will accept
  6. ; 4 commands:
  7. ; I [number] - to insert a number
  8. ; S [number] - to search for a number
  9. ; P - to print out the contents of the tree
  10. ; E - to exit the program
  11. ; only integers between 0 and 9 will be accepted
  12. ; each item in tree will have a root, one byte to hold number (0-9),
  13. ; then one blank byte, then
  14. ; a left pointer 4 bytes, and a right pointer 4 bytes.
  15. ; size of node is therefore 10 bytes
  16. ; data is displacement of 0
  17. ; left branch is displacement of 2
  18. ; right branch is displacement of 6 
  19.  
  20. ; NOTE: regarding input
  21. ; the program will ignore any number of spaces
  22. ; a number is required after the I and S commands (error message will be displayed)
  23. ; anything after the P or E command will be ignored. (no error message)
  24. ; only 1 digit numbers will be stored.  The program will notify the user
  25. ; of what was inserted or searched for.
  26. ; Only the first digit will be used (ie The number 95 will be a 9)
  27.  
  28.  
  29. ; Loading origin is at $1000
  30.             org $1000                   ;loading origin
  31.  
  32. ;print title
  33.             jsr ClearScreen             ;clear the screen
  34.             movea #Title,a0             ;move address of title into a0
  35.             jsr WriteString             ;print title
  36.  
  37. ; initialize registers
  38.             move.l #0,a2                ;zero out a2
  39.             move.l #0,a3                ;zero out a3
  40.             move.l #0,a4                ;zero out a4
  41.  
  42. ; read from keyboard
  43. BEGIN       jsr WriteEOL                    ;print blank line
  44.             movea #INPUT,a0                 ;get ready to print prompt
  45.             jsr WriteString                 ;prompt
  46.             movea #In_String,a0             ;move the address into a0
  47.             jsr ReadString                  ;read a string from the keyboard
  48.             jsr WriteEOL                    ;carriage return
  49.             movea #In_String,a0             ;designate the locate to store string
  50.  
  51. ;break apart string, command goes into d2, number (if applicable) into d3
  52.             move.l #0,d2                    ;zero out d2
  53.             move.l #0,d3                    ;zero out d3
  54.  
  55. ;get command put in d2
  56.             move.l #0,d5                    ;zero out d5
  57. LOOP1       move.b 0(a0,d5),d4              ;move next character into d4
  58.             cmpi.b #$20,d4                  ;if space            
  59.             beq.b INC1                      ;then go to next character
  60.             move.b d4,d2                    ;else store this as command
  61.             bra OUT1                        ;jump out of loop
  62. INC1        addq.l #1,d5                    ;move to next character
  63.             bra LOOP1                       ;loop thru again
  64.  
  65. OUT1        addq.l #1,d5                    ;move to next char after command
  66.  
  67. ;get the number put in d3
  68. LOOP2       move.b 0(a0,d5),d4              ;move next char into d4
  69.             cmpi.b #$20,d4                  ;if space
  70.             beq.b INC2                      ;then go to next char
  71.             move.b d4,d3                    ;else store this as the number
  72.             bra OUT2                        ;jump out of loop
  73. INC2        addq.l #1,d5                    ;increment character counter
  74.             bra LOOP2                       ;loop thru again
  75.  
  76. OUT2        cmpi.b #$50,d2                  ;if command is Print
  77.             beq CHECK                       ;go to Check
  78.             cmpi.b #$45,d2                  ;if command is Exit
  79.             beq CHECK                       ;go to check
  80.             cmpi.b #0,d3                    ;if number is $0
  81.             beq.b BAD                       ;then it is I or S with no number
  82.  
  83. ;check what was read in
  84. CHECK       cmpi.b #$49,d2                ;if insert command
  85.             beq.w INSERT                  ;then Insert the number 
  86.             cmpi.b #$53,d2                ;if search command
  87.             beq.w SEARCH                  ;then search for the number
  88.             cmpi.b #$50,d2                ;if print command
  89.             beq.w PRINT                   ;then print contents of tree
  90.             cmpi.b #$45,d2                ;if exit command 
  91.             beq.w EXIT                    ;then exit
  92.  
  93. BAD         jsr WriteEOL                  ;print blank line
  94.             movea #BadInput,a0            ;get ready to print bad input message
  95.             jsr WriteString               ;print out error message
  96.             bra BEGIN                     ;no valid input try again
  97.  
  98.  
  99. ;insert section ******************************************
  100. INSERT      cmpa #0,a2                    ;see if empty
  101.             beq.w START                   ;then insert this number into tree
  102.  
  103.             movea a2,a3                   ;move tree pointer to top of tree.
  104. COMPARE     cmp.w 0(a3),d3                ;compare number to insert with root
  105.             beq.w EXIST                   ;if exist then print so.
  106.             blt.b GO_LEFT                 ;if less than, go left
  107.             bgt.b GO_RIGHT                ;if greater than, go right
  108.  
  109. GO_LEFT     cmpi.l #0,2(a3)               ;see if null
  110.             bne 1$                        ;no then jmp to move pointer
  111.             move.l SPACE,d0               ;move space into d0
  112.             jsr malloc                    ;allocate memory
  113.             move.l a0,2(a3)               ;set the left pointer to this new location.
  114.             move.l 2(a3),a3               ;move the tree pointer to left branch
  115.             move.w d3,0(a3)               ;move number into data field
  116.             move.l #0,2(a3)               ;zero out left branch
  117.             move.l #0,6(a3)               ;zero out right branch
  118.             bra END_INSERT                ;jump out of insert section
  119. 1$          move.l 2(a3),a3               ;move the tree pointer to left branch
  120.             bra COMPARE                   ;compare again   
  121.  
  122. GO_RIGHT    cmpi.l #0,6(a3)               ;see if null
  123.             bne 1$                        ;no then jmp to move pointer
  124.             move.l SPACE,d0               ;move spaceinto d0
  125.             jsr malloc                    ;allocate memory
  126.             move.l a0,6(a3)               ;set the right pointer to this new location.
  127.             move.l 6(a3),a3               ;move the tree pointer to right branch
  128.             move.w d3,0(a3)               ;move number into data field
  129.             move.l #0,2(a3)               ;zero out left branch
  130.             move.l #0,6(a3)               ;zero out right branch
  131.             bra END_INSERT                ;jump out of insert section
  132. 1$          move.l 6(a3),a3               ;move the tree pointer to right branch
  133.             bra COMPARE                   ;compare again   
  134.  
  135. EXIST       movea #String1,a0             ;move word 'integer ' into a0
  136.             jsr WriteString               ;print word 'integer '
  137.             move.b d3,INTEGER             ;move d3 to INTEGER 
  138.             movea #INTEGER,a0             ;move integer into a0 to print
  139.             jsr WriteString               ;print integer
  140.             movea #String2,a0             ;move string2 into a0
  141.             jsr WriteString               ;print rest of line
  142.             bra BEGIN                     ;jump out of insert
  143.                                                         
  144. START       move.l SPACE,d0               ;set d0 for space
  145.             jsr malloc                    ;allocate memory
  146.             movea a0,a2                   ;make a2 point to the newly allocated memory
  147.             move.w d3,0(a2)               ;move the number into the root.
  148.             move.l #0,2(a2)               ;zero out left pointer
  149.             move.l #0,6(a2)               ;zero out right pointer
  150.             bra END_INSERT                ;finished with insert
  151.  
  152. END_INSERT  movea #String1,a0             ;move word 'integer ' into a0
  153.             jsr WriteString               ;print word 'integer '
  154.             move.b d3,INTEGER             ;move d3 to INTEGER 
  155.             movea #INTEGER,a0             ;move integer into a0 to print
  156.             jsr WriteString               ;print integer
  157.             movea #String6,a0             ;move string6 into a0
  158.             jsr WriteString               ;print rest of line
  159.             bra BEGIN                     ;go back to read another command
  160. ; end insert section *******************************************
  161.  
  162.  
  163. ; search section ************************************************
  164. SEARCH      cmpa #0,a2                    ;test if tree is empty
  165.             beq 5$                        ;if empty print not found
  166.  
  167.             move a2,a3                    ;move the tree pointer to top
  168. 1$          cmp.w 0(a3),d3                ;compare the data with search        
  169.             beq 4$                        ;if equal then print found
  170.             blt 2$                        ;if less than go left
  171.             bgt 3$                        ;if greater than go right
  172.  
  173. 2$          cmpi.l #0,2(a3)               ;see if left branch is null
  174.             beq 5$                        ;if null then print not found
  175.             move.l 2(a3),a3               ;move to left branch
  176.             bra 1$                        ;compare again
  177.  
  178. 3$          cmpi.l #0,6(a3)               ;see if right branch is null
  179.             beq 5$                        ;if null then print not found
  180.             move.l 6(a3),a3               ;move to right branch
  181.             bra 1$                        ;compare again
  182.  
  183. 4$          movea #String1,a0             ;move word into a0
  184.             jsr WriteString               ;print word
  185.             move.b d3,INTEGER             ;move d3 to INTEGER 
  186.             movea #INTEGER,a0             ;move integer into a0 to print
  187.             jsr WriteString               ;print integer
  188.             movea #String3,a0             ;move string2 into a0
  189.             jsr WriteString               ;print rest of line
  190.             bra END_SRCH                  ;jump out of insert
  191.  
  192. 5$          movea #String1,a0             ;move word 'integer ' into a0
  193.             jsr WriteString               ;print word 'integer '
  194.             move.b d3,INTEGER             ;move d3 to INTEGER 
  195.             movea #INTEGER,a0             ;move integer into a0 to print
  196.             jsr WriteString               ;print integer
  197.             movea #String4,a0             ;move string2 into a0
  198.             jsr WriteString               ;print rest of line
  199.             bra END_SRCH                  ;jump out of insert
  200.           
  201. END_SRCH    bra BEGIN                     ;read in another command          
  202. ;end of search section    *************************************
  203.  
  204.  
  205. ;PRINT section ************************************************
  206. ;print uses pre-order traversal (root-left-right)
  207. PRINT       cmpa #0,a2                    ;see if tree is empty
  208.             beq EMPTY                     ;if empty then print empty
  209.             movea a2,a3                   ;move the tree pointer to top
  210.             movea #STACK,a4               ;initialize stack pointer
  211.             movea #Tree,a0                ;move the word 'tree' to print
  212.             jsr WriteString               ;print out the word 'tree'
  213.  
  214. ;print root
  215. AGAIN       move.b 1(a3),ROOT             ;move number into root 
  216.             movea #ROOT,a0                ;move address of root into a0 
  217.             jsr WriteString               ;print root
  218.  
  219. ;push right branch (if not null)            
  220.             cmpi.l #0,6(a3)               ;if right is null
  221.             beq.b 1$                      ;then don't push onto stack
  222.             move.l 6(a3),-(a4)            ;else push right branch on to stack
  223.             
  224. ;go right (if not null)
  225. 1$          cmpi.l #0,2(a3)               ;see if left is null
  226.             beq.b POP                     ;if null then pop off stack
  227.             move.l 2(a3),a3               ;else move pointer to left branch
  228.             bra AGAIN                     ;go thru again
  229.  
  230. ;pop right branch (until no more left)
  231. POP         cmpi.l #0,(a4)                ;see if stack is empty
  232.             beq.b END_PRNT                ;if empty done 
  233.             move.l (a4)+,a3               ;pop off stack the last right branch
  234.             bra AGAIN                     ;go thru cycle again
  235.  
  236. EMPTY       movea #String5,a0             ;move empty into a0 to print
  237.             jsr WriteString               ;print string5
  238.             bra END_PRNT                  ;end print section
  239.  
  240. END_PRNT    jsr WriteEOL                  ;print blank line
  241.             bra BEGIN                     ;read in another command
  242. ; end print section *********************************************
  243.  
  244. ;provided code for proper execution and exit
  245. EXIT        movea #GoodBye,a0             ;get ready to say good bye 
  246.             jsr WriteString               ;print goodbye
  247.  
  248.             Move #228,D7          ;The code to end the program
  249.             Trap #14              ;Returns control to the operating system
  250.             NOLIST                ;No list turns off listing so you only get your code.
  251.             DC.W    0             ;Forces a Word Boundary.
  252.             Include "samples.asm" ;Includes our routines in your program.
  253.             LIST
  254.  
  255.  
  256. ;define constants and variables
  257. SPACE       dc.l 10                     ;size of node, 10 bytes
  258.  
  259. ;define strings
  260. Title       dc.b '*********************************************',13,10
  261.             dc.b '*  Binary Search Tree                       *',13,10
  262.             dc.b '*  Program 3                 Thomas Seddon  *',13,10
  263.             dc.b '*********************************************',13,10,0
  264. String1     dc.b 'Integer ',0
  265. String2     dc.b ' already exists in the tree.',13,10,0
  266. String3     dc.b ' was found in the search tree.',13,10,0
  267. String4     dc.b ' was not found.',13,10,0
  268. String5     dc.b 'The tree is empty.',13,10,0
  269. String6     dc.b ' was inserted into the tree.',13,10,0
  270. BadInput    dc.b 'Bad Command! Try Again.',13,10,0
  271. INPUT       dc.b 'Command> ',0
  272. Tree        dc.b 'Tree Contents -> ',0
  273. GoodBye     dc.b 'GoodBye!',13,10,0
  274.  
  275. In_String   ds.w 40                   ;this is string for the readstring routine
  276.  
  277. I           dc.b 'I'
  278. S           dc.b 'S'
  279. P           dc.b 'P'
  280. E           dc.b 'E'
  281.             
  282.             ds.l 20                     ;make enough space for stack
  283. STACK       dc.l 0                      ;beginning of stack
  284.  
  285. INTEGER     ds.b 1                      ;temporary storage for integer
  286.             dc.b 0                      ;null character
  287. ROOT        ds.b 1                      ;temp storage for root to print
  288.             dc.b ' '                    ;store comma
  289.             dc.b 0                      ;null character
  290.             end                         ;end of program
  291. ; End of program ************************************************************
  292.